package com.leetcode.August;

import java.util.*;

/**
 * @Description: 207. 课程表
 * 每次只能选你能上的课
 * 每次只能选入度为 0 的课，因为它不依赖别的课，是当下你能上的课。
 * 假设选了 0，课 3 的先修课少了一门，入度由 2 变 1。
 * 接着选 1，导致课 3 的入度变 0，课 4 的入度由 2 变 1。
 * 接着选 2，导致课 4 的入度变 0。
 * 现在，课 3 和课 4 的入度为 0。继续选入度为 0 的课……直到选不到入度为 0 的课。
 * @Author: Mr.Fxy
 * @CreateTime: 2024-08-13 09:45
 */
public class LC207课程表 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] inDegree = new int[numCourses];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < prerequisites.length; i++) {
            inDegree[prerequisites[i][0]]++;//入度
            //依赖的课程
            map.putIfAbsent(prerequisites[i][1], new ArrayList<>());
            //在对应被依赖课程key添加依赖key的课程
            map.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        //入度为零放入
        Queue<Integer> que = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                que.offer(i);
            }
        }
        //弹出已选课程，在map找到依赖它的课程，在入度数组--
        while (!que.isEmpty()) {
            int course = que.poll();
            numCourses--;
            for (Integer next : map.getOrDefault(course, new ArrayList<>())) {
                if (--inDegree[next] == 0) {
                    que.offer(next);
                }

            }
        }
        return numCourses == 0;
    }
}
